package week07

// 547. 省份数量
// https://leetcode-cn.com/problems/number-of-provinces/

func findCircleNum(isConnected [][]int) int {
	var n = len(isConnected)
	var fa = make([]int, n)
	for i := range fa {
		fa[i] = i
	}
	for i := range isConnected {
		for j := range isConnected[i] {
			if isConnected[i][j] == 1 {
				unionSet(fa, i, j)
			}
		}
	}
	var ans = 0
	for i, p := range fa {
		if p == i {
			ans++
		}
	}
	return ans
}

func find(fa []int, x int) int {
	if fa[x] != x {
		fa[x] = find(fa, fa[x])
	}
	return fa[x]
}

func unionSet(fa []int, x, y int) {
	fa[find(fa, x)] = find(fa, y)
}